# Boyer-Moore

## Solution naïve

Instruction à dénombrer: `if text[i + j] != pattern[j]:`

- Dans le meilleur cas : le premier caractère du motif n'est pas présent dans
le texte ; exemple : `texte = "abcdefgh"` et `motif = "i…"`.  
→ Dans ce scénario, l'instruction est exécutée `(n - m + 1) * 1` fois ; en considèrant
que `m` est très petit par rapport à `n`, la complexité est linéaire — en `O(n)`.

- Dans le pire cas, le motif correspond presque parfaitement à chaque position
du texte, mais échoue systématiquement au dernier caractère ; exemple : `texte = "aaaaaaa"`
et `motif = "aaab"`.  
→ Dans ce scénario, l'instruction est exécutée `(n - m + 1) * m` fois, approximé
en `O(n.m)`.

Le problème est que si on trouve une non-correspondance à la fin du motif,
ce n'est qu'après avoir comparé `m` caractères, et on ne décale la texte que
d'un seul cran.


## Solution de Boyer-Moore

On remarque que la complexité effective est meilleure que la solution naïve :
14 < 22 pour le texte "loren irsum doler amar" et le motif "amar".

Dans le pire cas, tous les caractères du motif correspondent, sauf le dernier
comparé (le premier du motif), et le caractère en non correspondance ne permet
qu'un décalage de 1 caractère à chaque itération. Exemple : `texte = "aaaaaaaaaaaa"`
et `motif = "baaa"`.
Dans ce scénario, l'algorithme effectue `(n - m + 1) * m` comparaisons (auxquelles
s'ajoutent les `m - 1` opération du précalcul - négligeables), et l'algorithme
naïf est bien meilleur (9 < 39)…

La complexité théorique reste en `O(n.m)`, mais il est généralement plus performant :
dans le meilleur cas, le décalage est de `m` à chaque itération, soit une
complexite de `n/m`, et en moyenne sa complexité est `Θ(n)` (`theta(n)`).